package sort;

import edu.princeton.cs.algs4.StdOut;

public class Shell extends Example {
  public static void sort(Comparable[] a) {
    int N = a.length;
    int h = 1; // 默认分组长度
    while (h < N / 3) {
      // 根据数组长度计算分组长度
      h = 3 * h + 1; // 1,4,13,40...
    }

    while (h >= 1) {
      StdOut.println("h = " + h);
      for (int i = h; i < N; i++) {
        // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]..之中
        for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
          exch(a, j, j - h);
          show(a);
        }
        show(a);
      }
      h = h / 3;
    }

  }

  public static void main(String[] args) {
    String str = "SHELLSORTEXAMPLE";
    String[] a = str.split("");
    show(a);
    Shell.sort(a);
  }
}
